/**
 * 48. Rotate Image 旋转图像
 * https://leetcode.com/problems/rotate-image/description/
 */
class RotateImage {
    /**
     * 方法：旋转图像
     * 通过先转置矩阵再水平翻转每一行来实现90度顺时针旋转
     * 
     * Args:
     *     matrix: int[][] - 输入的n x n二维矩阵
     * 
     * Returns:
     *     void - 直接修改原矩阵
     * 
     * Time: O(n^2) - 需要遍历矩阵中的所有元素
     * Space: O(1) - 原地修改，不需要额外空间
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 1. 转置 (i, j) -> (j,i)
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){// 遍历对角线下方元素
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        // 2. 行翻转(j, i) -> (j, n-1-i)
        for(int[] row : matrix){
            for(int j = 0; j < n / 2; j++){ // 遍历左半元素
                int tmp = row[j];
                row[j] = row[n - 1 - j];
                row[n - 1 - j] = tmp;
            }
        }
    }
}